package algotithm.leetcode.tree.test1367;

 class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode (int val) {
        this.val = val;
    }

}
/**
 * @author zhouyanxiang
 * @Date 2021-02-2021/2/6-17:57
 * @URL https://leetcode-cn.com/problems/linked-list-in-binary-tree/
 * @Title 1367. 二叉树中的列表
 */
public class Solution {

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(4);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(8);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = null;

        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(4);
        TreeNode node3 = new TreeNode(4);
        TreeNode node4 = new TreeNode(2);
        TreeNode node5 = new TreeNode(2);
        TreeNode node6 = new TreeNode(1);
        TreeNode node7 = new TreeNode(6);
        TreeNode node8 = new TreeNode(8);
        TreeNode node9 = new TreeNode(1);
        TreeNode node10 = new TreeNode(3);

        node1.left = node2;
        node1.right = node3;
        node2.left = null;
        node2.right = node4;
        node3.left = node5;
        node3.right = null;
        node4.left = node6;
        node4.right = null;
        node5.left = node7;
        node5.right = node8;
        node6.left = null;
        node6.right = null;
        node7.left = null;
        node7.right = null;
        node8.left = node9;
        node8.right = node10;
        node9.left = null;
        node9.right = null;
        node10.left = null;
        node10.right = null;

        Solution solution = new Solution();
        boolean subPath = solution.isSubPath(listNode1, node1);
        System.out.println(subPath);
    }

    public boolean isSubPath(ListNode head, TreeNode root) {
        if (root == null) {
            return false;
        }
        return dfs(head,root) || isSubPath(head,root.left) || isSubPath(head,root.right);
    }

    public boolean dfs(ListNode head, TreeNode root) {
        if (head == null) {
            return true;
        }
        if (root == null) {
            return false;
        }
        if (head.val != root.val) {
            return false;
        }
        return dfs(head.next,root.left) || dfs(head.next,root.right);
    }

}
